/*******************************************************************************
* FileName:         Graph.h
* Author:           李智铭
* Student Number:   3022206093
* Date:             2024/12/4 17:00:00
* Version:          v1.0
* Description:      Data Structure Experiment #13
*******************************************************************************/
#include "Graph.h"
#include <iostream>
#include <climits>
#include <queue>
using namespace std;

Graph::Graph(int max_v):max_count(max_v), adjmax(max_v + 1, vector<int>(max_v + 1, 0)) {}

Graph::~Graph(){
    //STL类自动管理内存
}

void Graph::addedge(int s, int t, int w){
    if(s > max_count || t > max_count){
        cout << "INVALID NODE ID" << endl;
        return;
    }

    if(!w) w = -1;
    adjmax[s][t] = w;
}

int Graph::getV(){
    int count = 0;
    for(int i = 1; i <= max_count; i++){
        bool has_edge = false;
        for(int j = 1; j <= max_count; j++){
            if(adjmax[i][j] != 0 || adjmax[j][i] != 0) {
                has_edge = true;
                break;
            }
        }
        if(has_edge) count++;
    }
    return count;
}


int* Graph::dijkstra(){
    int start = 1;
    vector<int> dist(max_count + 1, INT_MAX);  // 初始化为无穷大
    dist[start] = 0;

    // 标记节点是否已被访问
    vector<bool> visited(max_count + 1, false);

    // 最小堆存储每次访问的节点
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push({0, start});  // 从源点开始

    while(!pq.empty()){
        // 获取当前距离最小的节点
        int u = pq.top().second;
        pq.pop();

        // 节点已被访问
        if(visited[u]) continue;
        visited[u] = true;

        for(int v = 1; v <= max_count; v++){
            // 存在边且v未被访问
            if(adjmax[u][v] != 0 && !visited[v]){
                // 更新源点到v的最短路径
                if(dist[v] > dist[u] + adjmax[u][v]){
                    dist[v] = dist[u] + adjmax[u][v];
                    pq.push({dist[v], v});  // 将v和更新后的距离推入优先队列
                }
            }
        }
    }

    int* ans = new int[max_count];
    for(int i = 1; i <= max_count; i++) {

        if(dist[i] == INT_MAX) {
            ans[i - 1] = -1;  // 使用-1表示无法到达
        } else {
            ans[i - 1] = dist[i];
        }
    }

    return ans;
}